#include <iostream>
#include <stack>
using namespace std;

class Sort
{
public:
	void InsertSort(int* p, int n)
	{
		for (int i = 0; i < n - 1; i++)
		{
			int end = i;
			int key = p[end + 1];
			while (end >= 0)
			{
				if (key < p[end])
				{
					p[end + 1] = p[end];
					end--;
				}
				else
				{
					break;
				}
			}
			p[end + 1] = key;
		}
	}

	void ShellSort(int* p, int n)
	{
		int gap = n;
		while (gap > 1)
		{
			gap /= 2;
			for (int i = 0; i < n - gap; i++)
			{
				int end = i;
				int key = p[end + gap];
				while (end >= 0)
				{
					if (key < p[end])
					{
						p[end + gap] = p[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				p[end + gap] = key;
			}
		}
	}

	void BubbleSort(int* p, int n)
	{
		for (int x = 0; x < n - 1; x++)
		{
			int cont = 1;
			for (int y = 0; y < n - x - 1; y++)
			{
				if (p[y] > p[y + 1])
				{
					cont = 0;
					Swap(&p[y], &p[y + 1]);
				}
			}
			if (cont == 1)
			{
				break;
			}
		}
	}

	void SelectSort(int* p, int n)
	{
		int left = 0;
		int right = n - 1;
		while (left < right)
		{
			int max = right;
			int min = left;
			for (int i = left; i <= right; i++)
			{
				if (p[i] > p[max])
				{
					max = i;
				}
				if (p[i] < p[min])
				{
					min = i;
				}
			}
			Swap(&p[min], &p[left]);
			if (max == left)
			{
				max = min;
			}
			Swap(&p[max], &p[right]);
			left++;
			right--;
		}
	}

	void HeapSort(int* p, int n)
	{
		for (int i = (n - 1 - 1) / 2; i > 0; i--)
		{
			AdjustDwon(p, n, i);
		}
		int end = n - 1;
		while (end > 0)
		{
			Swap(&p[end], &p[0]);
			AdjustDwon(p, end, 0);
			end--;
		}
	}

	void MergeSort(int* p, int n)
	{
		int* root = (int*)malloc(sizeof(int) * n);
		_MergeSort(p, root, 0, n - 1);
		free(root);
	}

	void MergeSortNonR(int* p, int n)
	{
		int* root = (int*)malloc(sizeof(int) * n);
		for (int gap = 1; gap < n; gap *= 2)
		{
			for (int i = 0; i < n; i += 2 * gap)
			{
				int begin1 = i;
				int end1 = gap + i - 1;
				int begin2 = gap + i;
				int end2 = i + 2 * gap - 1;
				int index = i;
				if (begin2 >= n)
				{
					break;
				}
				if (end2 >= n)
				{
					end2 = n - 1;
				}
				while (begin1 <= end1 && begin2 <= end2)
				{
					if (p[begin1] < p[begin2])
					{
						root[index++] = p[begin1++];
					}
					else
					{
						root[index++] = p[begin2++];
					}
				}
				while (begin1 <= end1)
				{
					root[index++] = p[begin1++];
				}
				while (begin2 <= end2)
				{
					root[index++] = p[begin2++];
				}
				memcpy(&p[i], &root[i], sizeof(int) * (end2 - i + 1));
			}
		}
	}

	void Print(int* p, int n)
	{
		for (int i = 0; i < n; i++)
		{
			cout << p[i] << " ";
		}
		cout << endl;
	}

private:
	void Swap(int* x1, int* x2)
	{
		int k = *x1;
		*x1 = *x2;
		*x2 = k;
	}

	void AdjustDwon(int* p, int n, int root)
	{
		int parent = root;
		int child = parent * 2 + 1;
		while (child < n)
		{
			if (child + 1 < n && p[child + 1] > p[child])
			{
				child++;
			}
			if (p[child] > p[parent])
			{
				Swap(&p[child], &p[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}

	void _MergeSort(int* p, int* root, int left, int right)
	{
		if (left >= right)
		{
			return;
		}
		int mid = (left + right) >> 1;
		_MergeSort(p, root, left, mid);
		_MergeSort(p, root, mid + 1, right);
		int begin1 = left;
		int end1 = mid;
		int begin2 = mid + 1;
		int end2 = right;
		int index = left;
		while (begin1 <= end1 && begin2 <= end2)
		{
			if (p[begin1] < p[begin2])
			{
				root[index++] = p[begin1++];
			}
			else
			{
				root[index++] = p[begin2++];
			}
		}
		while (begin1 <= end1)
		{
			root[index++] = p[begin1++];
		}
		while (begin2 <= end2)
		{
			root[index++] = p[begin2++];
		}
		memcpy(&p[left], &root[left], sizeof(int) * (right - left + 1));
	}
};

class Qsort
{
public:
	void Print(int* p, int n)
	{
		for (int i = 0; i < n; i++)
		{
			cout << p[i] << " "  ;
		}
		cout << endl;
	}

	void QuickSort(int *p,int n)
	{
		//PartSort1(p, 0, n - 1);
		//PartSort2(p, 0, n - 1);
		//PartSort3(p, 0, n - 1);
		PartSort4(p, 0, n - 1);
	}

	void QuickSortNonR(int* a, int left, int right)
	{
		stack<int> st;
		st.push(left);
		st.push(right);
		while (!st.empty())
		{
			int end = st.top();
			st.pop();
			int begin = st.top();
			st.pop();
			int key = PartSort5(a,begin,end);
			if (begin < key - 1)
			{
				st.push(begin);
				st.push(key - 1);
			}
			if (key + 1 < end)
			{
				st.push(key + 1);
				st.push(end);
			}
		}
	}


private:
	void Swap(int* x1, int* x2)
	{
		int k = *x1;
		*x1 = *x2;
		*x2 = k;
	}

	int GetMid(int* p, int left, int right)
	{
		int mid = (left + right) >> 1;
		if (p[mid] > p[left])
		{
			if (p[mid] < p[right])
			{
				return mid;
			}
			else if (p[left] > p[right])
			{
				return left;
			}
			else
			{
				return right;
			}
		}
		if (p[mid] < p[left])
		{
			if (p[mid] > p[right])
			{
				return mid;
			}
			else if (p[left] < p[right])
			{
				return left;
			}
			else
			{
				return right;
			}
		}
	}

	void PartSort1(int* p, int left, int right)
	{
		if (left >= right)
		{
			return;
		}
		int index = GetMid(p, left, right);
		Swap(&p[left], &p[index]);
		int begin = left;
		int end = right;
		int keyi = p[left];
		while (begin < end)
		{
			while (begin < end && p[end] >= keyi)
			{
				end--;
			}
			while (begin < end && p[begin] <= keyi)
			{
				begin++;
			}
			Swap(&p[begin], &p[end]);
		}
		Swap(&p[left], &p[begin]);
		PartSort1(p, left, begin - 1);
		PartSort1(p, begin + 1, right);
	}

	void PartSort2(int* p, int left, int right)
	{
		if (left >= right)
		{
			return;
		}
		int index = GetMid(p, left, right);
		Swap(&p[left], &p[index]);
		int prev = left;
		int begin = left;
		int end = right;
		int keyi = p[left];
		while (begin < end)
		{
			while (begin < end && p[end] >= keyi)
			{
				end--;
			}
			p[prev] = p[end];
			prev = end;
			while (begin < end && p[begin] <= keyi)
			{
				begin++;
			}
			p[prev] = p[begin];
			prev = begin;
		}
		p[prev] = keyi;
		PartSort2(p, left, begin - 1);
		PartSort2(p, begin + 1, right);
	}

	int PartSort5(int* p, int left, int right)
	{
		int index = GetMid(p, left, right);
		Swap(&p[left], &p[index]);
		int prev = left;
		int begin = left;
		int end = right;
		int keyi = p[left];
		while (begin < end)
		{
			while (begin < end && p[end] >= keyi)
			{
				end--;
			}
			p[prev] = p[end];
			prev = end;
			while (begin < end && p[begin] <= keyi)
			{
				begin++;
			}
			p[prev] = p[begin];
			prev = begin;
		}
		p[prev] = keyi;
		return prev;
	}

	void PartSort3(int* p, int left, int right)
	{
		if (left >= right)
		{
			return;
		}
		int index = GetMid(p, left, right);
		Swap(&p[left], &p[index]);
		int begin = left;
		int end = begin + 1;
		int keyi = p[left];
		while (end <= right)
		{
			if (p[end] < keyi)
			{
				Swap(&p[end], &p[++begin]);
			}
			end++;
		}
		Swap(&p[begin], &p[left]);
		PartSort3(p, left, begin - 1);
		PartSort3(p, begin + 1, right);
	}
	void PartSort4(int* p, int left, int right)
	{
		if (left >= right)
		{
			return;
		}
		int index = GetMid(p, left, right);
		Swap(&p[left], &p[index]);
		int begin = left;
		int end = right;
		int keyi = p[left];
		int c = left + 1;
		while (c <= end )
		{
			if (p[c] < keyi)
			{
				Swap(&p[c], &p[begin]);
				begin++;
			}
			else if (p[c] > keyi)
			{
				Swap(&p[c], &p[end]);
				end--;
			}
			else
			{
				c++;
			}
		}
		PartSort4(p, left, begin - 1);
		PartSort4(p, end + 1, right);
	}

};

int main()
{
	int p[10] = { 9,8,7,6,5,4,3,2,1,0 };
	Qsort q;
	q.QuickSort(p, 10);
	q.Print(p, 10);
	//Sort q;
	//q.HeapSort(p, 10);
	//q.BubbleSort(p, 10);
	//q.InsertSort(p, 10);
	//q.SelectSort(p, 10);
	//q.ShellSort(p, 10);
	//q.MergeSort(p, 10);
	//q.MergeSortNonR(p, 10);
	//q.Print(p, 10);
	return 0;
}